package algorithm.search;

/**
 * 二分查找
 *
 * @author 杨 强
 * @package algorithm.search
 * @createTime 2023-02-27 21:50
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] num = new int[]{1,2,3,4,5,6,7,10,9,10};
        int value = 10;
        int ret = binarySearch02(num, value);
        System.out.println(ret);
    }

    /**
     * 二分查找之递归版本
     * @param a
     * @param target
     * @return
     */
    public static int binarySearch02(int[] a, int target){
        return f(a, target, 0, a.length - 1);
    }

    private static int f(int[] a, int target, int i, int j){
        if (i > j) {
            return -1;
        }

        int m = (i + j) >>> 1;

        if (target > a[m]){
            return f(a, target, m + 1, j);
        }if (target < a[m]){
            return f(a, target, i, m - 1);
        }else {
            return m;
        }
    }


    /**
     * 基础版本二分查找
     * @param a 有序的目标数组
     * @param target 需要查询的值
     * @return 查询到目标值就返回目标值的索引,查询不到就返回-1
     */
    public static int binarySearch01(int[] a, int target){
        if (a == null || a.length == 0){
            return -1;
        }

        int i = 0;
        int j = a.length - 1;

        while (i <= j){
            int m = (i + j) >>> 1;
            if (a[m] > target){
                j = m - 1;
            } else if(a[m] < target){
                i = m + 1;
            }else {
                return a[m];
            }
        }
        return -1;
    }

    /**
     * 二分查找:有重复值取最左边的下标
     * @param a 有序的目标数组
     * @param target 需要查询的值
     * @return 查询到目标值就返回目标值的索引,查询不到就返回-1
     */
    public static int binarySearchLeftmost(int[] a, int target){
        if (a == null || a.length == 0){
            return -1;
        }

        int index = -1;

        int i = 0;
        int j = a.length - 1;

        while (i <= j){
            int m = (i + j) >>> 1;
            if (a[m] > target){
                j = m - 1;
            } else if(a[m] < target){
                i = m + 1;
            }else {
                // 记录候选者位置
                index = m;
                // 然后继续向左查找,如果在左边又查询到了目标值说明这个目标值的下标更小,就替换候选者
                j = m - 1;
            }
        }
        return index;
    }



}
